#include <stdio.h>
#include <conio.h>
#include "templatevector.h"
#include <Windows.h>	// SetConsoleCursorPosition

// drawing stuff to the screen
void setCursor(int x, int y)
{
	COORD p = {x,y};
	SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE),p);
}
void setColor(int c)
{
	SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),c);
}

// a simple 2D vector used to describe locations on the console screen
struct V2D
{
	short x, y;
	V2D(int x, int y):x(x),y(y){}
	V2D():x(0),y(0){}
};

// prototype, telling the compiler that there will be a class
class GraphNode;

// describes a 1 way relationship between 2 nodes
struct GraphEdge
{
	GraphNode * from;	// which node we move from
	GraphNode * to;		// which node we move to
	float cost;			// the cost associated with the movement
	void draw();	// prototype the function
	GraphEdge(GraphNode * from, GraphNode * to, float cost)
		:from(from),to(to),cost(cost){}
	GraphEdge()
		:from(0),to(0),cost(0){}
};
// is the main unit in our NP (non-polynomial time) complete problem
class GraphNode
{
private:
	// what is printed out on the console
	int id;
	// where in the console to print this
	V2D pos;
public:
	int mark;
	// the list of connections to other nodes (neighbors)
	TemplateVector<GraphEdge> edges;
	int getID(){return id;}
	TemplateVector<GraphEdge> * getEdges(){return &edges;}
	// accesor
	V2D getPosition(){return pos;}
	void drawSelf()
	{
		setCursor(pos.x, pos.y);
		putchar(id);
	}
	// draws the node to the screen, after drawing its edges
	void draw()
	{
		for(int i = 0; i < edges.size(); ++i)
		{
			edges.get(i).draw();
		}
		drawSelf();
	}
	GraphNode(int id, V2D pos):id(id),pos(pos),mark(0){}
	GraphNode():id(0),mark(0){}
	// adds another node as a neighbor
	void addNeighbor(GraphNode * n)
	{
		V2D dist(this->pos.x-n->pos.x, this->pos.y-n->pos.y);
		// adding the manhattan distance
		edges.add(GraphEdge(this, n, (float)dist.x+dist.y));
	}
};
// homebrew absolute value
//inline int abs(int const & num){return (num < 0)?-num:num;}
#define abs(a)	((a<0)?-a:a)

// must be defined AFTER both GraphEdge AND GraphNode, because it uses both
void GraphEdge::draw()
{
	// determine the distance between the two nodes
	V2D fpos= from->getPosition();
	V2D tpos= to->getPosition();
	V2D delta(tpos.x-fpos.x, tpos.y-fpos.y);
	// make a cursor that draws a line between them
	V2D moving = fpos;
	// while that cursor has not reached its destination
	while(abs(delta.x) > 0 || abs(delta.y) > 0)
	{
		// draw a character at the cursor
		setCursor(moving.x, moving.y);
		putchar('.');
		// move the cursor (and update the movement-left also)
		int d;
		// only move in a given dimension if that move is not 0
		if(abs(delta.x) != 0 && abs(delta.x)+1 >= abs(delta.y))
		{
			moving.x += (d = delta.x/abs(delta.x));
			delta.x -= d;
		}
		if(abs(delta.y) != 0 && abs(delta.y)+1 >= abs(delta.x))
		{
			moving.y += (d = delta.y/abs(delta.y));
			delta.y -= d;
		}
	}
}

#include "traversal.h"

int main(int argc, char** argv)
{
//	printf("Graphs");
	// node ID and position 
	int nodesAndPositions[] ={
	'A',  9, 0,
	'B', 12, 1,
	'C',  6, 3,
	'D',  8, 6,
	'E', 12,10,
	'F', 13, 6,
	'G', 17, 3,
	'H', 17,11,
	'I', 15,15,
	'J', 10,13,
	'K',  7,10,
	'L',  4, 7,
	'M',  0,11,};
	int nodesAndPositionsCount = sizeof(nodesAndPositions)/sizeof(nodesAndPositions[0]);

	TemplateVector<GraphNode> nodes;
	// create the nodes
	nodes.setSize(nodesAndPositionsCount);
	for(int i = 0; i < nodes.size(); i += 3)
	{
		nodes.set(i/3, GraphNode(nodesAndPositions[i],
			V2D(nodesAndPositions[i+1], nodesAndPositions[i+2])));
	}


	// how nodes are connected ([0] is connected to [n+1])
	char * nodeConnections[] = {
	"AD",		"DAFEK",		"BC",		"CADL",
	"EFIJ",		"FBDGHE",		"GF",		"HI",
	"IHJ",		"JKI",			"KJDM",		"LM",
	"MK",
	};
	int nodesConnectionsCount = sizeof(nodeConnections)/sizeof(nodeConnections[0]);
	// create the connections
	int nodeIndex, neighborIndex;
	GraphNode * n0;
	GraphNode * n1;
	for(int i = 0; i < nodesConnectionsCount; ++i)
	{
		// great example of abstraction
		nodeIndex = nodeConnections[i][0]-'A';
		n0 = &nodes.get(nodeIndex);
		int len = strlen(nodeConnections[i]);
		for(int a = 1; a < len; ++a)
		{
			neighborIndex = nodeConnections[i][a]-'A';
			n1 = &nodes.get(neighborIndex);
			n0->addNeighbor(n1);
		}
	}

	bool running = true;
	int userInput;
	GraphNode * selected = &nodes.get(0);
	int colorNormal = FOREGROUND_RED|FOREGROUND_GREEN|FOREGROUND_BLUE, 
		colorSelected = FOREGROUND_RED|FOREGROUND_GREEN|FOREGROUND_INTENSITY,
		colorTraverse = FOREGROUND_BLUE|FOREGROUND_GREEN|FOREGROUND_INTENSITY;
	TemplateVector<GraphNode*> dftraversal;
	TemplateVector<GraphNode*> bftraversal;
	depthFirst(selected, dftraversal);
	breadthFirst(selected, bftraversal);
	while(running)
	{
		// draw
		// draw the entire graph
		setColor(colorNormal);
		for(int i = 0; i < nodes.size(); ++i)
		{
			nodes.get(i).draw();
		}
		// draw the selected node
		setColor(colorSelected);
		selected->draw();
		// draw the options for traversal
		TemplateVector<GraphEdge> * edges = selected->getEdges();
		setColor(colorTraverse);
		for(int i = 0; i < edges->size(); ++i)
		{
			edges->get(i).to->drawSelf();
			putchar('\b');
			putchar(i+'0');
		}
		setCursor(0, 20);
		printf("depth:  ");
		for(int i = 0; i < dftraversal.size(); ++i)
		{
			printf("%c ", dftraversal.get(i)->getID());
		}
		putchar('\n');
		printf("breadth:");
		for(int i = 0; i < bftraversal.size(); ++i)
		{
			printf("%c ", bftraversal.get(i)->getID());
		}
		putchar('\n');
		// input
		userInput = _getch();
		// logic
		switch(userInput)
		{
		case 27:	running = false;	break;
		default:
			// if a traversal option key was hit
			if(userInput >= '0' && userInput <= '9')
			{
				// determine which node the user wants to travel to
				int nextIndex = userInput - '0';
				// if it is a valid node
				if(nextIndex < edges->size())
				{
					// travel there.
					selected = edges->get(nextIndex).to;
					dftraversal.clear();
					bftraversal.clear();
					depthFirst(selected, dftraversal);
					breadthFirst(selected, bftraversal);
				}
			}
		}
	}
	_getch();
	return 0;
}